package 十一树的实际应用;

import java.io.*;
import java.util.*;

/**
 * @Author XuZhuHong
 * @CreateTime 2021/9/28 17:43
 * 赫夫曼编码的压缩和解压缩
 */
public class HuffmanCode {
    public static void main(String[] args) {
//        //把下面这个字符串用赫夫曼树存储
        String str = "i like like like java do you like a java";
        byte[] bytes = str.getBytes();

//        //调用函数将这个转成一个NodeCode的列表
//        //每个元素都是一个nodecode节点
//        ArrayList< NodeCode > list = bytesToArray(str);
//        Collections.sort(list);
//        System.out.println("==============================根据字符串创建的节点列表=============================");
//        System.out.println(list.toString());
//        //用节点列表创建一个赫夫曼树
//        NodeCode root = createHuffmanCode(list);
//        //根据赫夫曼树得到赫夫曼编码
//        HashMap< Byte, String > codes = getCodes(root);
//        System.out.println("==============================赫夫曼的码=============================");
//        System.out.println("生成的赫夫曼编码" + codes);
//        System.out.println("==============================字符串对应压缩过后的码=============================");
//        byte[] bytes = zip(codes, str);
//        System.out.println(Arrays.toString(bytes));
//        System.out.println("==============================上面所有方法的封装=============================");

        System.out.println("==============================字符串直接转赫夫曼码=============================");
        byte[] bytes1 = bytesToHuffmanByte(bytes);
        System.out.println(Arrays.toString(bytes1));
        System.out.println("==============================赫夫曼的对应的码=============================");
        System.out.println(huffmanCodeMap);
        System.out.println("==============================赫夫曼对应的码解密============================");
        byte[] decode = decode(huffmanCodeMap, bytes1);
        //把字节数组转换成对应的string然后输出
        System.out.println(new String(decode));

    }


    //编写一个方法，完成对压缩文件的解压
    /**
     *
     * @param zipFile 准备解压的文件
     * @param dstFile 将文件解压到哪个路径
     */
    public static void unZipFile(String zipFile, String dstFile) {

        //定义文件输入流
        InputStream is = null;
        //定义一个对象输入流
        ObjectInputStream ois = null;
        //定义文件的输出流
        OutputStream os = null;
        try {
            //创建文件输入流
            is = new FileInputStream(zipFile);
            //创建一个和  is关联的对象输入流
            ois = new ObjectInputStream(is);
            //读取byte数组  huffmanBytes
            byte[] huffmanBytes = (byte[])ois.readObject();
            //读取赫夫曼编码表
            Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();

            //解码
            byte[] bytes = decode(huffmanCodes, huffmanBytes);
            //将bytes 数组写入到目标文件
            os = new FileOutputStream(dstFile);
            //写数据到 dstFile 文件
            os.write(bytes);
        } catch (Exception e) {
            // TODO: handle exception
            System.out.println(e.getMessage());
        } finally {

            try {
                os.close();
                ois.close();
                is.close();
            } catch (Exception e2) {
                // TODO: handle exception
                System.out.println(e2.getMessage());
            }

        }
    }

    //编写方法，将一个文件进行压缩
    /**
     *
     * @param srcFile 你传入的希望压缩的文件的全路径
     * @param dstFile 我们压缩后将压缩文件放到哪个目录
     */
    public static void zipFile(String srcFile, String dstFile) {

        //创建输出流
        OutputStream os = null;
        ObjectOutputStream oos = null;
        //创建文件的输入流
        FileInputStream is = null;
        try {
            //创建文件的输入流
            is = new FileInputStream(srcFile);
            //创建一个和源文件大小一样的byte[]
            byte[] b = new byte[is.available()];
            //读取文件
            is.read(b);
            //直接对源文件压缩
            byte[] huffmanBytes = bytesToHuffmanByte(b);
            //创建文件的输出流, 存放压缩文件
            os = new FileOutputStream(dstFile);
            //创建一个和文件输出流关联的ObjectOutputStream
            oos = new ObjectOutputStream(os);
            //把 赫夫曼编码后的字节数组写入压缩文件
            oos.writeObject(huffmanBytes); //我们是把
            //这里我们以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用
            //注意一定要把赫夫曼编码 写入压缩文件
            oos.writeObject(huffmanCodeMap);


        }catch (Exception e) {
            // TODO: handle exception
            System.out.println(e.getMessage());
        }finally {
            try {
                is.close();
                oos.close();
                os.close();
            }catch (Exception e) {
                // TODO: handle exception
                System.out.println(e.getMessage());
            }
        }

    }


    //编写一个方法，完成对压缩数据的解码

    /**
     * @param huffmanCodes 赫夫曼编码表 map
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return 就是原来的字符串对应的数组
     */
    private static byte[] decode(Map< Byte, String > huffmanCodes, byte[] huffmanBytes) {

        //首先把字节数组转成字符串数组
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < huffmanBytes.length; i++) {
            String s;
            //调用一个方法 把对应的byte转换成二进制字符串
            if (i == huffmanBytes.length - 1) {
                s = byteToBitString(false, huffmanBytes[i]);
            } else {
                s = byteToBitString(true, huffmanBytes[i]);
            }
            stringBuilder.append(s);
        }

        //把huffmanCodes这个存放value的集合key和value反转
        HashMap< String, Byte > byteHashMap = new HashMap<>();
        for (Map.Entry< Byte, String > byteStringEntry : huffmanCodes.entrySet()) {
            byteHashMap.put(byteStringEntry.getValue(), byteStringEntry.getKey());
        }

        ArrayList< Byte > list = new ArrayList<>();
        //从string中找数据  在反转过后的代码中进行匹配  如果匹配到  放到列表中
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 0;
            Byte aByte = null;
            while (true) {
                String substring = stringBuilder.substring(i, i + count);
                aByte = byteHashMap.get(substring);
                if (aByte != null) {
                    break;
                }
                count++;
            }
            i += count;
            list.add(aByte);
        }
        //把得到的list元素放入byte数组中
        int i = 0;
        byte[] b = new byte[list.size()];
        for (Byte aByte : list) {
            b[i++] = aByte;
        }
        return b;
    }

    /**
     * 将一个 byte 转成一个二进制的字符串, 如果看不懂，可以参考我讲的 Java 基础 二进制的原码，反码，补
     * 码
     *
     * @param b    传入的 byte
     * @param flag 标志是否需要补高位如果是 true ，表示需要补高位，如果是 false 表示不补, 如果是最后一个
     *             字节，无需补高位
     * @return 是该 b 对应的二进制的字符串，（注意是按补码返回）
     */
    private static String byteToBitString(boolean flag, byte b) {
        //使用变量保存 b
        int temp = b; //将 b 转成 int
        //如果是正数我们还存在补高位
        if (flag) {
            temp |= 256; //按位与 256 1 0000 0000 | 0000 0001 => 1 0000 0001
        }
        String str = Integer.toBinaryString(temp); //返回的是 temp 对应的二进制的补码
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }

    /**
     * 传入一个字符串 返回其对应的赫夫曼字节数组19:21:37
     *
     * @param bytes
     * @return
     */
    public static byte[] bytesToHuffmanByte(byte[] bytes) {

//        //根据字符串里面字符出现的次数创建一个节点列表
//        ArrayList< NodeCode > list = bytesToArray(str);
//        //用得到的列表创建一个赫夫曼树
//        NodeCode root = createHuffmanCode(list);
//        //根据赫夫曼树得到赫夫曼编码
//        HashMap< Byte, String > codes = getCodes(root);
//        //根据编码和字符串得到赫夫曼的字节数组
//        byte[] bytes = zip(codes, str);
//        return bytes;

        return zip(getCodes(createHuffmanCode(bytesToArray(bytes))), bytes);
    }

    /**
     * 把字符串赫夫曼编码和对应的字符串传入进来  然后对字符串进行压缩  2021年9月29日18:41:38
     *
     * @param codes 对应的赫夫曼编码的集合
     * @param bytes   字符串对应的
     * @return
     */
    public static byte[] zip(HashMap< Byte, String > codes, byte[] bytes) {
        //创建一个stringBuilder储存字符串对应的赫夫曼编码
        StringBuilder stringBuilder = new StringBuilder();

        for (byte aByte : bytes) {
            //在传入的对应的表里面 找到对应的码 并且添加到stringbuilder中
            stringBuilder.append(codes.get(aByte));
        }

        //创建一个新的数组  数组的长度取决于string的长度  因为怕不够  所以在最后需要添加一位
        int len = (stringBuilder.length() + 7) / 8;
        //创建一个新的bytes数组  用来存放压缩后的数据
        byte[] bytes1 = new byte[len];
        int index = 0;//用来记录存储的位置

        //以8位为一组  然后把他压缩到新的byte中
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            //判断最后一次是否越界  如果越界就直接截取到最后即可
            if ((i + 8) > stringBuilder.length()) {
                bytes1[index++] = (byte) Integer.parseInt(stringBuilder.substring(i), 2);
            } else {
                bytes1[index++] = (byte) Integer.parseInt(stringBuilder.substring(i, i + 8), 2);
            }
        }
        return bytes1;
    }

    /**
     * 传入赫夫曼树的root节点  得到每个节点对应的赫夫曼编码
     *
     * @param root
     * @return
     */
    public static HashMap< Byte, String > getCodes(NodeCode root) {
        getCodes(root, "", new StringBuilder());
        return huffmanCodeMap;
    }

    //赫夫曼编码实现2021年9月29日09:48:17
    // 建一个集合来存储每一个字节对应的赫夫曼编码  这个必须是全局的 因为 每次到了子节点  都会存储 对应的byte和路线的str
    static HashMap< Byte, String > huffmanCodeMap = new HashMap<>();

    /**
     * @param node          节点
     * @param code          向左走为0  向右1
     * @param stringBuilder 上一个元素的编码  用于记录每次走的步骤
     */
    //方法的实现
    public static void getCodes(NodeCode node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        //在这个的最后加上他
        stringBuilder1.append(code);
        //首先判断这个节点是否为空  如果为空 就不操作了
        if (node != null) {
            //判断是不是子节点
            if (node.value == null) {
                getCodes(node.left, "0", stringBuilder1);
                getCodes(node.right, "1", stringBuilder1);
            } else {
                huffmanCodeMap.put(node.value, stringBuilder1.toString());
            }
        }
    }

    /**
     * @param strBytes 传入字符串
     * @return 返回一个根据字符串的权重（出现次数越频繁权重越高）创建的节点列表
     */
    //把字符串转换为arraylist的节点数组
    public static ArrayList< NodeCode > bytesToArray(byte[] strBytes) {

        //用一个map来记录字母出现的权重
        HashMap< Byte, Integer > byteIntegerHashMap = new HashMap<>();

        //计数所有字母出现的个数保存到map集合
        for (byte strByte : strBytes) {
            Integer count = byteIntegerHashMap.get(strByte);
            //如果为空那么就添加一个
            if (count == null) {
                byteIntegerHashMap.put(strByte, 1);
            } else {
                //如果不为空就证明之前已经添加进去一个字符了  只需要给他的权重加一即可
                byteIntegerHashMap.put(strByte, count + 1);
            }
        }

        ArrayList< NodeCode > array = new ArrayList<>();
        //把集合里面已经得到的权重数据 转化为列表
        for (Map.Entry< Byte, Integer > entry : byteIntegerHashMap.entrySet()) {
            array.add(new NodeCode(entry.getKey(), entry.getValue()));
        }

        //返回添加好的权重回去
        return array;
    }

    /**
     * @param arrayList 节点的列表
     * @return 赫夫曼树的root节点
     */
    //用一个列表创建赫夫曼树
    public static NodeCode createHuffmanCode(ArrayList< NodeCode > arrayList) {
        while (arrayList.size() > 1) {
            //排序
            Collections.sort(arrayList);
            //取出前两个节点
            NodeCode left = arrayList.get(0);
            NodeCode right = arrayList.get(1);
            //用前两个节点创建一个新的节点  这个节点不是叶子节点他的baty码为null
            NodeCode node = new NodeCode(null, left.weight + right.weight);
            //把这个新节点的左右指向之前的两个
            node.left = left;
            node.right = right;

            //把新的这个元素添加到这个节点
            arrayList.add(node);
            //移出最少的两个节点
            arrayList.remove(0);
            arrayList.remove(0);
        }
        return arrayList.get(0);

    }

}

class NodeCode implements Comparable< NodeCode > {
    Byte value;
    int weight;
    NodeCode left;
    NodeCode right;


    public NodeCode(Byte value, int weight) {
        this.value = value;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(NodeCode o) {
        return this.weight - o.weight;
    }


    public void preOrder() {
        preOrder(this);
    }

    //前序遍历的方法
    public void preOrder(NodeCode node) {
        if (node == null) {
            return;
        }
        System.out.println(node);
        if (node.left != null) {
            preOrder(node.left);
        }
        if (node.right != null) {
            preOrder(node.right);
        }
    }
}